//给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 
//请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。 
//
// 
//
// 示例： 
//
// matrix = [
//   [ 1,  5,  9],
//   [10, 11, 13],
//   [12, 13, 15]
//],
//k = 8,
//
//返回 13。
// 
//
// 
//
// 提示： 
//你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。 
// Related Topics 堆 二分查找 
// 👍 529 👎 0
#include <iostream>
#include <vector>
#include <queue>

using namespace std;



//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        //移动k步 每步塞进一个有序的set弹出top

        //方法一
        //vector<int> res;
        //for (int i = 0; i < matrix.size(); ++i) {
        //    for (int j = 0; j < matrix[0].size(); ++j) {
        //        res.push_back(matrix[i][j]);
        //    }
        //}
        //sort(res.begin(),res.end());
        //return res[k - 1];

        int n = matrix.size();
        priority_queue<int> pq;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                pq.push(matrix[i][j]);
                if (pq.size() > k){
                    pq.pop();
                }
            }
        }
        return pq.top();
    }
};
//leetcode submit region end(Prohibit modification and deletion)
